<template>
  <ExamPaper :items="paper" :name="title" @update:answers="val => (finalAnswers = val)" />
</template>

<script setup>
import { ref, onMounted, computed } from 'vue'
import ExamPaper from '@/components/ExamPaper.vue'
// 使用路由meta中的name作为标题
import { useRoute } from 'vue-router'
const route = useRoute()
const title = computed(() => {
  return route.meta.title || '算法题库'
})

const paper = ref([
    {
        question: `
        堆（中等）
        347. 前 K 个高频元素
        中等
        相关标签
        premium lock icon
        相关企业
        给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

        

        示例 1：

        输入：nums = [1,1,1,2,2,3], k = 2

        输出：[1,2]

        示例 2：

        输入：nums = [1], k = 1

        输出：[1]

        示例 3：

        输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2

        输出：[1,2]

        

        提示：

        1 <= nums.length <= 105
        k 的取值范围是 [1, 数组中不相同的元素的个数]
        题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
        

        进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
        `,
        answer: `
        function deal1(nums,k) {
          const map = new Map();
          for (let index = 0; index < nums.length; index++) {
            const chart = nums[index];
            const oldValue = map.get(chart)||0;
            map.set(chart,oldValue+1)
          }
          const arr = Array.from(map);
          arr.sort((a,b)=>{
            return a[1]>b[1]?-1:1
          })
          return arr.slice(0,k).map(item=>item[0])
        }
        // 时间复杂度为 O(n)+O(m log m)+O(k)=O(n + m log m)  （k ≤ m ≤ n），简化为 O(n log m)
        // 空间复杂度为 O(m)
        `,
        remark: `
        
        
        下面这个是
        ai给的时间复杂度更低
        function topKFrequent(nums, k) {
          const freq = new Map();          // O(n)
          for (const v of nums) freq.set(v, (freq.get(v)||0)+1);

          // 桶：下标 = 出现次数，值 = 该次数的所有数字
          const bucket = Array(nums.length + 1).fill(null).map(_=>[]);
          for (const [num, cnt] of freq) bucket[cnt].push(num);   // O(m)

          const ans = [];
          for (let cnt = bucket.length - 1; cnt >= 0 && ans.length < k; --cnt) {
            ans.push(...bucket[cnt]);      // 共收集 k 个
          }
          return ans.slice(0, k);          // 保险截断
        }
        时间：O(n + m + k) = O(n)（k ≤ m ≤ n）
        空间：O(n + m) = O(n)

        `
    },
    {
      question:` 
      双指针
      42. 接雨水
      困难
      相关标签
      premium lock icon
      相关企业
      给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

      

      示例 1：
      <img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png" style="height: 161px; width: 412px;">


      输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
      输出：6
      解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
      示例 2：

      输入：height = [4,2,0,3,2,5]
      输出：9
      

      提示：

      n == height.length
      1 <= n <= 2 * 104
      0 <= height[i] <= 105
      `,
      answer:`
      function deal1(numArr){
        const copyNumArr = [...numArr];
        let preMax = 0;
        let preMaxIndex = -1;
        let waterNum = 0;
        for(let i=0;i<copyNumArr.length;i++){
          if(copyNumArr[i]>=preMax){
            for(let pointer=preMaxIndex+1;pointer<i;pointer++){
              const poor = preMax-copyNumArr[pointer];
              waterNum+=poor
            }
            preMax = copyNumArr[i];
            preMaxIndex = i;
          }else{
            for(let pointer=i-1;pointer>preMaxIndex;pointer--){
              const poor = copyNumArr[i]-copyNumArr[pointer];
              if(poor>0){
                waterNum+=poor
                copyNumArr[pointer] = copyNumArr[i];
              }else{
                break
              }
            }
          }
        }
        console.log(waterNum);
        return waterNum
      }
      deal1([0,1,0,2,1,0,1,3,2,1,2,1])
      deal1([4,2,0,3,2,5])
      `,
      remark:`
      出现对称性质的问题，考虑使用双指针。
      一层循环遍历，另一层双指针遍历。当然还有符号对称性问题，可以在一层循环中同时处理。
      但不变的是，对于双指针，左右指针的移动是一致的，且左右指针的移动是一致的，可以使用左右指针的移动，来解决对称问题。
      也就是先入栈再出栈来解决对称问题。
      `
    },
    {
      question:`
      广度优先搜索
      127. 单词接龙
      困难
      相关标签
      premium lock icon
      相关企业
      字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

      每一对相邻的单词只差一个字母。
      对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
      sk == endWord
      给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

      
      示例 1：

      输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
      输出：5
      解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
      示例 2：

      输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
      输出：0
      解释：endWord "cog" 不在字典中，所以无法进行转换。
      

      提示：

      1 <= beginWord.length <= 10
      endWord.length == beginWord.length
      1 <= wordList.length <= 5000
      wordList[i].length == beginWord.length
      beginWord、endWord 和 wordList[i] 由小写英文字母组成
      beginWord != endWord
      wordList 中的所有字符串 互不相同
      `,
      answer:`
      function deal3(beginWord,endWord,wordList) {
        let set = new Set(wordList);
        if(!set.has(endWord)){
          console.log(0)
          return 0
        }
        
        const penddingList = [{word:beginWord,step:1}];
        let canUse = [];
        let newCanUse= [...wordList]
        let result = 0;
        let isArrive = false;
        while(penddingList.length){
          if(isArrive){
            break
          }
          const item = penddingList.splice(0,1)[0];
          canUse = newCanUse
          newCanUse = [];
          console.log(canUse)
          while (canUse.length) {
            const citem = canUse.splice(0,1)[0]
            const isAdjoinResult = isAdjoin(item.word,citem)
            if(isAdjoinResult){
              console.log(citem)
              penddingList.push({word:citem,step:item.step+1})
              if(citem == endWord){
                result = item.step+1;
                isArrive = true
              }
            }else{
              newCanUse.push(citem)
            }
            if(isArrive){
              break
            }
          }
        }
        console.log(result);
        return result;

        function isAdjoin(str1,str2) {
          let str1Length = str1.length;
          let str1Pointer = 0;
          let str2Length = str2.length;
          let str2Pointer = 0;
          let diffNum = 0;
          if(str1Length-str2Length>1 || str2Length-str1Length>1){
            return false
          }
          for (let index = 0; index < str1Length; index++) {
            if(str1[str1Pointer] == str2[str2Pointer]){
              str1Pointer+=1;
              str2Pointer+=1
            }else{
              if(str1Length>str2Length){
                str1Pointer+=1
              }else if(str1Length<str2Length){
                str2Pointer+=1
              }else{
                str1Pointer+=1
                str2Pointer+=1
              }
              diffNum+=1
              if(diffNum>1){
                break
              }
            }
          }
          if(diffNum<2){
            return true
          }else{
            return false
          }
        }
      }
      `,
      remark:`
      写个思路吧，有点困了。用循环递归去做，最坏的情况是 n*(n-1)*(n-2).... 也就是 O(n!)但是大概率有些通路走不通，所以时间复杂度不会这么高。
      ai说时间复杂度为 O(n^2)，这是因为 n^2 的子问题，可以用动态规划来做，时间复杂度为 O(n^2)
      广度搜索 的第二个循环 尽量使用 可确定的 循环数目 不要再依赖 n
      ai的答案
      ✅ 推荐的标准 BFS 解法（JavaScript 版）
      JavaScript
      function ladderLength(beginWord, endWord, wordList) {
        const wordSet = new Set(wordList);
        if (!wordSet.has(endWord)) return 0;

        const queue = [[beginWord, 1]]; // [当前单词, 当前步数]
        const visited = new Set([beginWord]);

        while (queue.length) {
          const [word, step] = queue.shift();

          for (let i = 0; i < word.length; i++) {
            for (let c = 97; c <= 122; c++) { // a-z
              const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);

              if (newWord === endWord) return step + 1;
              if (wordSet.has(newWord) && !visited.has(newWord)) {
                visited.add(newWord);
                queue.push([newWord, step + 1]);
              }
            }
          }
        }

        return 0;
      }
      ✅ 总结
      表格
      复制
      维度	你的代码	推荐 BFS 解法
      正确性	基本正确	✅ 完全正确
      效率	❌ 低效 O(N²×M)	✅ 高效 O(N×M×26)
      可读性	❌ 较差	✅ 简洁清晰
      是否推荐	❌ 不推荐	✅ 推荐


      如果没有“所有单词长度相等”这一前提，题目就变成了最小编辑距离为 1 的图最短路径问题，此时“一次转换”可以允许：
      插入一个字母
      删除一个字母
      替换一个字母（Levenshtein 距离 = 1）
      你的原代码（双指针 isAdjoin）确实试图处理长度不等的情况，但：
      逻辑复杂、容易漏边界；
      时间复杂度高达 O(N²×L)，N 是单词数，L 是平均长度；
      仍不是“最优”做法。
      真正高效、可维护的做法是：预先建图 + 标准 BFS，而不是每次在线性扫描整本字典。
      下面给出工业界/竞赛界常用的两种方案，按数据规模选用。
      方案 A：小规模（N ≤ 500，单词长度 ≤ 10）
      把字典去重后做成 Set。
      对任意两个单词，直接算 Levenshtein 距离；
      距离 == 1 就连一条无向边。
      跑一遍 BFS（起点 beginWord，终点 endWord）。
      建图复杂度 O(N²×L)，内存 O(N²)，
      但 N≤500 时 250 000 条边完全吃得下。
      代码最短，不易出错。
      方案 B：中大规模（N ≤ 5000，L ≤ 10）
      在线“两两比对”太慢，改为**“邻居生成器”**：
      对字典里的每一个单词 w，枚举所有距离为 1 的邻居：
      替换：逐位置换 26 字母 → L×26 个
      插入：逐位置插 26 字母 → (L+1)×26 个
      删除：逐位置删字母 → L 个
      总共 O(L×26) 个候选，看哪些候选出现在字典里即可。
      这样单次扩展从 O(N×L) 降到 O(26×L)，整体复杂度
      O(N×26×L)，比你的 O(N²×L) 快一个数量级。
      代码骨架（JS，允许长度不等）
      JavaScript
      复制
      function oneStepNeighbors(w, set) {
        const ans = new Set();
        const L = w.length;
        // 1. 替换
        for (let i = 0; i < L; ++i)
          for (let c = 97; c <= 122; ++c) {
            const t = w.slice(0, i) + String.fromCharCode(c) + w.slice(i + 1);
            if (set.has(t)) ans.add(t);
          }
        // 2. 插入
        for (let i = 0; i <= L; ++i)
          for (let c = 97; c <= 122; ++c) {
            const t = w.slice(0, i) + String.fromCharCode(c) + w.slice(i);
            if (set.has(t)) ans.add(t);
          }
        // 3. 删除
        for (let i = 0; i < L; ++i) {
          const t = w.slice(0, i) + w.slice(i + 1);
          if (set.has(t)) ans.add(t);
        }
        return [...ans];
      }

      function ladderLength(beginWord, endWord, wordList) {
        const set = new Set(wordList);
        if (!set.has(endWord)) return 0;

        const q = [[beginWord, 1]];
        const vis = new Set([beginWord]);

        while (q.length) {
          const [w, d] = q.shift();
          for (const nxt of oneStepNeighbors(w, set)) {
            if (nxt === endWord) return d + 1;
            if (!vis.has(nxt)) {
              vis.add(nxt);
              q.push([nxt, d + 1]);
            }
          }
        }
        return 0;
      }
      小结
      表格
      复制
      场景	推荐做法
      长度相等（原题）	26×L 替换邻居 + 标准 BFS
      长度不等（扩展）	生成“编辑距离=1”邻居 + 标准 BFS
      你的原双指针扫描	❌ 慢、复杂、易错，任何场景都不是最优
      `
    }
])
function deal3(beginWord,endWord,wordList) {
  let set = new Set(wordList);
  if(!set.has(endWord)){
    console.log(0)
    return 0
  }
  
  const penddingList = [{word:beginWord,step:1}];
  let canUse = [];
  let newCanUse= [...wordList]
  let result = 0;
  let isArrive = false;
  while(penddingList.length){
    if(isArrive){
      break
    }
    const item = penddingList.splice(0,1)[0];
    canUse = newCanUse
    newCanUse = [];
    console.log(canUse)
    while (canUse.length) {
      const citem = canUse.splice(0,1)[0]
      const isAdjoinResult = isAdjoin(item.word,citem)
      if(isAdjoinResult){
        console.log(citem)
        penddingList.push({word:citem,step:item.step+1})
        if(citem == endWord){
          result = item.step+1;
          isArrive = true
        }
      }else{
        newCanUse.push(citem)
      }
      if(isArrive){
        break
      }
    }
  }
  console.log(result);
  return result;

  function isAdjoin(str1,str2) {
    let str1Length = str1.length;
    let str1Pointer = 0;
    let str2Length = str2.length;
    let str2Pointer = 0;
    let diffNum = 0;
    if(str1Length-str2Length>1 || str2Length-str1Length>1){
      return false
    }
    for (let index = 0; index < str1Length; index++) {
      if(str1[str1Pointer] == str2[str2Pointer]){
        str1Pointer+=1;
        str2Pointer+=1
      }else{
        if(str1Length>str2Length){
          str1Pointer+=1
        }else if(str1Length<str2Length){
          str2Pointer+=1
        }else{
          str1Pointer+=1
          str2Pointer+=1
        }
        diffNum+=1
        if(diffNum>1){
          break
        }
      }
    }
    if(diffNum<2){
      return true
    }else{
      return false
    }
  }
}


onMounted(() => {
  deal3('hit','cog',["hot","dot","dog","lot","log","cog"])
  deal3('hit','cog',["hot","dot","dog","lot","log"])
})


const finalAnswers = ref([])   // 实时收集到的答案
</script>